/**
 * By calculating, the number must be less than 100.000
 * A = n1n2...nn
 * B = n1^5 + n2^5 + ... nn^5
 *  A = B ( A > 10...0 ( n -1)
 *  B < n x 9^5 
 */

/**
 * @author TrinhNX
 * @start_date	: 2015/04/23
 * @end_date 	:
 */
public class Euler030 {

	/*
	 * Ideal, we will check in range
	 * 132 - 300
	 * 1000 -> 7000
	 * 10000 -> STOP
	 */
	public static void main(String[] args) {
		final int STOP = 295245;
		// Well, try with String first
		// Test again with Integer
		System.out.println("Start");
		final long start = System.currentTimeMillis();
		//		String text;
		int sum = 0;
		// With for: Time is about 300.
		//		for (int i = 1000; i < 7000; i++) {
		//			if (isValid(i))
		//				sum += i;
		//		}
		//		for (int i = 10000; i < STOP; i++) {
		//			if (isValid(i))
		//				sum += i;
		//		}
		// Not for, about 303 ms , well, need optimize the calculation
		int value = 132;
		int temp_sum, m, n;
		while (++value < STOP) {
			temp_sum = 0;
			m = 0;
			n = value;
			// Optimize 3: Well reduce to 240 ms :D
			// Optimize 4: Well, 16ms :v ,not using pow()
			do {
				m = n % 10;
				n = n / 10;
				temp_sum += (m * m * m * m * m);
			} while (n > 0);
			//			text = Integer.toString(value);
			//			for (char c : text.toCharArray()) {
			//				temp_sum += ((int) Math.pow((c - '0'), 5));
			//			}
			if (temp_sum == value) {
				sum += temp_sum;
			}
		}
		System.out.println(sum);
		System.out.println("End after : " + (System.currentTimeMillis() - start));
	}

	/**
	 * @author		: TrinhNX
	 * @param number
	 * @return
	 * @start_date	: 2015/04/23
	 * @end_date	:
	 */
	private static boolean isValid(final int number) {
		int temp_sum = 0;
		for (char c : Integer.toString(number).toCharArray()) {
			temp_sum += ((int) Math.pow((c - '0'), 5));
		}
		if (temp_sum == number) {
			System.out.println("Value: " + number);
			return true;
		}
		return false;
	}
}
